﻿#pragma once
#include <mutex>
#include <list>
#include <vector>
#include <iostream>
#include <assert.h>
#include "as_mutex.h"
#ifdef AS_RAND
#include "as_rand.h"
#endif

template<class Obj, class Mutex, class Alloc = std::allocator<Obj> >
class SafeList
{
public:
	SafeList() = default;
	virtual ~SafeList() = default;
	typedef typename std::list<Obj, Alloc>::iterator iterator;
	typedef typename std::list<Obj, Alloc>::const_iterator const_iterator;

	virtual void push_back(Obj &o)
	{
		std::lock_guard<Mutex> lock(m_);
		l_.emplace_back(o);
	}

	virtual void push_back(const Obj &o)
	{
		std::lock_guard<Mutex> lock(m_);
		l_.emplace_back(o);
	}

	virtual void push_back(const Obj &&o)
	{
		std::lock_guard<Mutex> lock(m_);
		l_.emplace_back(o);
	}

	template<typename... Objs>
	void emplace_back(Objs &&...o)
	{
		std::lock_guard<Mutex> lock(m_);
		l_.emplace_back(std::forward<Objs>(o)...);
	}

	virtual Obj pop_back()
	{
		std::lock_guard<Mutex> lock(m_);
		Obj &o = l_.back();
		l_.pop_back();
		return o;
	}

	virtual Obj pop_front()
	{
		std::lock_guard<Mutex> lock(m_);
		Obj &o = l_.front();
		l_.pop_front();
		return o;
	}

	virtual Obj front()
	{
		std::lock_guard<Mutex> lock(m_);
		return l_.front();
	}

	virtual Obj back()
	{
		std::lock_guard<Mutex> lock(m_);
		return l_.back();
	}

	virtual Obj reverse()
	{
		std::lock_guard<Mutex> lock(m_);
		l_.reverse();
		return l_.front();
	}

	virtual bool empty()
	{
		std::lock_guard<Mutex> lock(m_);
		return l_.empty();
	}

	virtual size_t size()
	{
		std::lock_guard<Mutex> lock(m_);
		return l_.size();
	}

	virtual void swap(SafeList<Obj, Mutex, Alloc> &tar)
	{
		std::lock_guard<Mutex> lock(m_);
		l_.swap(tar.l_);
	}

	virtual iterator begin()
	{
		std::lock_guard<Mutex> lock(m_);
		return l_.begin();
	}

	virtual iterator end()
	{
		std::lock_guard<Mutex> lock(m_);
		return l_.end();
	}

private:
	std::list<Obj, Alloc> l_;
	Mutex m_;
};

//跳表
#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */
#define ZSKIPLIST_MAX_SEARCH 10


template<class Obj>
struct SkipNode
{
	SkipNode(int lv, Obj o) : obj(o), front(lv, nullptr) {}
	Obj obj;
	std::vector<SkipNode *> front;
};


template<class Obj, class Mutex = NullMutex, class Compare = std::less<Obj>, class Alloc = std::allocator<SkipNode<Obj> > >
class SkipList
{
public:
	typedef SkipNode<Obj> Node;
	SkipList()
	{
		head_ = alloc_.allocate(sizeof(Node));
		::new (static_cast<void *>(head_)) Node(ZSKIPLIST_MAXLEVEL, Obj());
	}

	~SkipList()
	{
		if (head_)
		{
			auto curr = head_;
			while (curr)
			{
				auto next = curr->front[0];
				curr->~Node();
				alloc_.deallocate(curr, sizeof(Node));
				curr = next;
			}
		}
	}

	void insert(const Obj &obj)
	{
		//组好要插入的组
		std::vector<Node *> upVec(ZSKIPLIST_MAXLEVEL, nullptr);

		Node *cur = head_;
		for (int i = curLv_ - 1; i >= 0; --i)
		{
			//获取最接近的一个节点
			while (cur->front[i] && compare_(cur->front[i]->obj, obj))
				cur = cur->front[i];
			//记录每一层最接近的节点
			upVec[i] = cur;
		}

		cur = cur->front[0];
		if (cur == nullptr || (compare_(cur->obj, obj) || compare_(obj, cur->obj)))
		{
			int lv = RandomLv();
			if (lv > curLv_)
			{
				//新一层
				for (int i = curLv_; i < lv; ++i)
				{
					upVec[i] = head_;
				}

				//设置最大层
				curLv_ = lv;
			}

			Node *newNode = alloc_.allocate(sizeof(Node));
			::new (static_cast<void *>(newNode)) Node(lv, obj);
			++count_;
			for (int i = 0; i < lv; ++i)
			{
				newNode->front[i] = upVec[i]->front[i];
				upVec[i]->front[i] = newNode;
			}
		}
	}

	void erase(const Obj &obj)
	{
		std::vector<Node *> upVec(ZSKIPLIST_MAXLEVEL, nullptr);
		Node *cur = head_;
		for (int i = curLv_ - 1; i >= 0; --i)
		{
			while (cur->front[i] && compare_(cur->front[i]->obj, obj))
				cur = cur->front[i];
			upVec[i] = cur;
		}

		cur = upVec[0]->front[0];
		if (cur && (!compare_(cur->obj, obj) && !compare_(obj, cur->obj)))
		{
			for (int i = 0; i < curLv_; ++i)
			{
				if (upVec[i]->front[i] == cur)
				{
					upVec[i]->front[i] = cur->front[i];
				}
			}

			while (curLv_ > 1 && head_->front[curLv_ - 1] == nullptr)
				curLv_--;

			cur->~Node();
			alloc_.deallocate(cur, sizeof(Node));
			--count_;
		}
	}

	bool find(const Obj &obj)
	{
		if (head_)
		{
			Node *cur = head_;
			for (int i = curLv_ - 1; i >= 0; --i)
			{
				while (cur->front[i] && compare_(cur->front[i]->obj, obj))
				{
					cur = cur->front[i];
				}
			}

			return cur && cur->front[0] && !compare_(cur->front[0]->obj, obj) && !compare_(obj, cur->front[0]->obj);
		}
		return false;
	}

	void display()
	{
		for (int i = 0; i <= curLv_; i++)
		{
			auto node = head_->front[i];
			std::cout << "Level " << i << ": ";
			while (node != nullptr) {
				std::cout << node->obj << " ";
				node = node->front[i];
			}
			std::cout << std::endl;
		}
	}

	int size() const { return count_; }
private:
	int RandomLv()
	{
		static const int threshold = ZSKIPLIST_P * RAND_MAX;
		int lv = 1;
#ifdef AS_RAND
		while (as::tools::random(1, RAND_MAX) < threshold)
			++lv;
#else
		while (std::rand() < threshold)
			++lv;
#endif
		return lv < ZSKIPLIST_MAXLEVEL ? lv : ZSKIPLIST_MAXLEVEL;
	}

	int curLv_ = 1;
	Node *head_ = nullptr;
	Compare compare_;
	Alloc alloc_;
	int count_ = 0;
};
